/*
Source : https://leetcode.com/problems/reverse-integer/
Author : nflush@outlook.com
Date   : 2016-05-09
*/
/*
29. Divide Two Integers  
Total Accepted: 66392 Total Submissions: 423417 Difficulty: Medium

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Subscribe to see which companies asked this question
*/
int getLBitPos(unsigned int num)
{
    const int pos[] = {
        0, 1, 2, 2,
        3, 3, 3, 3,
        4, 4, 4, 4,
        4, 4, 4, 4};
    int ret = 28;
    while(0 == pos[num >> ret]) {
        ret -= 4;
    }
    return ret + pos[num >> ret];
}

int divide(int dividend, int divisor)
{
    int          ret = 0;
    int          minus = 0;
    unsigned int udividend = dividend;
    unsigned int udivisor = divisor;
    if(0 == divisor || dividend == 0) {
        return 0;
    }
    if(dividend < 0) {
        minus = 1;
        udividend = 0 - dividend;
    }
    if(divisor < 0) {
        minus ^= 1;
        udivisor = 0 - divisor;
    }
    while(!(udivisor & 1)) {
        udividend >>= 1;
        udivisor >>= 1;
    }
    if(udivisor == 1) {
        return minus ? 0 - udividend : udividend > 2147483647 ? 2147483647 : udividend;
    }
    while(udividend >= udivisor) {
        int bisCount = getLBitPos(udividend) - getLBitPos(udivisor);
        if(udividend >= (udivisor << bisCount)) {
            udividend -= (udivisor << bisCount);
            ret += 1 << bisCount;
        } else {
            udividend -= (udivisor << (bisCount - 1));
            ret += 1 << (bisCount - 1);
        }
    }
    return minus ? 0 - ret : ret;
}

class Solution
{
private:
    int getLBitPos(unsigned int num)
    {
        const int pos[] = {
            0, 1, 2, 2,
            3, 3, 3, 3,
            4, 4, 4, 4,
            4, 4, 4, 4};
        int ret = 28;
        while(0 == pos[num >> ret]) {
            ret -= 4;
        }
        return ret + pos[num >> ret];
    }

public:
    int divide(int dividend, int divisor)
    {
        int          ret = 0;
        int          minus = 0;
        unsigned int udividend = dividend;
        unsigned int udivisor = divisor;
        if(0 == divisor || dividend == 0) {
            return 0;
        }
        if(dividend < 0) {
            minus = 1;
            udividend = 0 - dividend;
        }
        if(divisor < 0) {
            minus ^= 1;
            udivisor = 0 - divisor;
        }
        if(udivisor == udividend) {
            return minus ? -1 : 1;
        } else if(udividend < udivisor) {
            return 0;
        }
        while(!(udivisor & 1)) {
            udividend >>= 1;
            udivisor >>= 1;
        }
        if(udivisor == 1) {
            return minus ? 0 - udividend : udividend > 2147483647 ? 2147483647 : udividend;
        }
        int udivisorpos = getLBitPos(udivisor);
        while(udividend >= udivisor) {
            int bisCount = getLBitPos(udividend) - udivisorpos;
            if(udividend >= (udivisor << bisCount)) {
                udividend -= (udivisor << bisCount);
                ret += 1 << bisCount;
            } else {
                udividend -= (udivisor << (bisCount - 1));
                ret += 1 << (bisCount - 1);
            }
        }
        return minus ? 0 - ret : ret;
    }
};